Machine learning is a form of artificial intelligence that is employed to allow computers to evolve behaviors based on empirical data. Machine learning may take advantage of training examples to capture characteristics of interest of their unknown underlying probability distribution. Training data may be seen as examples that illustrate relations between observed variables. A major focus of machine learning research is to automatically learn to recognize complex patterns and make intelligent decisions based on data.
One main difficulty in machine learning lies in the fact that the set of all possible behaviors, given all possible inputs, is too large to be covered by a set of training data. Hence, a machine learning model must generalize from the training data so as to be able to produce a useful output in new cases.
One example of machine learning is traditional structured prediction (SP). Traditional SP is a single model approach to dependent output. With SP, once an input feature vector x is specified, a single correct output vector z can be fully specified. Thus the output vector z is fully conditioned on the input feature vector x and the different output components of output vector z (z1, z2, . . . ) are conditionally independent of each other given the input feature vector x. Thus, the probability of z1 given x is equal to the probability of z1 given x and z2, or p(z1|x)=p(z1|x, z2). However, traditional SP cannot handle an interdependent relationship between different output components. In addition, traditional SP cannot handle a problem having multiple correct output decisions for a given input.
The subject matter claimed herein is not limited to embodiments that solve any disadvantages or that operate only in environments such as those described above. Rather, this background is only provided to illustrate one example technology area where some embodiments described herein may be practiced.